1. Field of the Invention
The present invention relates to the field of expert systems and, more specifically, to the field of expert system analysis through structured knowledge representation in single and parallel processing systems including those used for natural language processing
2. Description of the Related Art
A generalized expert system typically includes a language or system for processing instructions and a representation of the data required for the application domain. A system for understanding natural language input from a user additionally includes specific processing instructions for interpreting natural language input and specific data which describes the user""s natural language. All of the above components interact tightly with one another, so that the design or selection of such components significantly affects the resulting system""s efficiency, correctness, robustness, and extensibility to advanced hardware platforms.
Natural language systems have processed the disambiguation of user input (e.g. deciding which among many possibly similar and plausible interpretations of the user""s input is correct) in numerous methods. An important aspect of each of those methods is to xe2x80x9cprunexe2x80x9d (e.g. reduce) the total number of candidate interpretations from an initial number which is quite large in a real-world implementation down to a very small number which is practical (e.g. time-efficient) to process. Those methods generally fall into two categories. The first defines criteria which each element of the input sentence must meet, usually by characteristics like number of arguments and in what part of a descriptive hierarchy it must reside (e.g. xe2x80x9cx must be some kind of machinexe2x80x9d). This method requires continuous and precise, time-consuming maintenance whenever an addition or change is made to the application domain""s data. The other method utilizes massive statistical computations on existing text to find other words that are often used with a given word, for example xe2x80x9cbankxe2x80x9d may be used in one sense with xe2x80x9cmoneyxe2x80x9d and in another sense with xe2x80x9criverxe2x80x9d. This method is unable to adapt to jargon or highly-specialized application domains while retaining reasonable recognition accuracy. Both of these methods have difficulties such as a decrease in speed of execution when the application domain is large (true for almost every commercial application) and poor success or uncertainty in understanding analogy, metaphor, and user input sentences which do not exactly conform to those expected by the system.
Current implementations for disambiguating natural language input typically are unable to utilize the parallel processing capabilities of multi-processor systems, and therefore create a processing bottleneck on advanced hardware.
The language or system for processing the specific natural language instructions is generally either frame-based, like most expert systems, or a series of sequential statements, often in a specialized language which has special data manipulation facilities like unification and list processing, such as LISP or Prolog.
Current expert systems are typically constructed as a series of xe2x80x9cframesxe2x80x9d which consist of the equivalent of an xe2x80x9cIFxe2x80x9d clause, describing the conditions under which this frame is true, and a xe2x80x9cTHENxe2x80x9d clause that describes the action to take when the xe2x80x9cIFxe2x80x9d clause is found to be true. Each frame is meant to contain an independent piece of knowledge about the application domain. If a variable, on which any frame depends, changes during execution, the entire frame is automatically placed on the xe2x80x9cagendaxe2x80x9d (execution list) to fully execute again. This is true whether or not that frame has previously executed. If the frame contains references to external modules written in a procedural language like C, which is usually needed for more complex actions than IF-THEN constructions, those modules are often unable to update the variables which affect the agenda. These expert systems are complex to program, difficult to extend into unique environments, and limited in their ability to combine knowledge from different sources, particularly during runtime.
Specialized languages like CLOS and Prolog do not automatically update any equivalent of an agenda when changing a variable, so that they are unable to have other instructions which depend on that variable updated. Updating is accomplished via such methods as manually-written routines associated with each variable for which this updating is desired. Clearly, this is repetitive and time-consuming.
Certain specialized languages like Prolog have xe2x80x9cunificationxe2x80x9d, or pattern-matching capabilities. Although such systems are somewhat flexible they are very slow in execution, so that special commands and programming methodologies need to be utilized to minimize the amount of unification that is actually done. Thus, these languages result in slow response times and are difficult to expand to large applications.
An issue with current implementations of both expert systems and unification-based languages is the need to introduce some level of sequencing of execution for the purposes of efficiency, initialization, grouping of similar procedures, and ease of constructing the data and instructions for the application. Examples of these are knowledge islands and execution priorities in expert systems and Prolog""s backtracking. This added-on sequencing defeats or overrides the automatic features described above and creates a requirement for much greater training and expertise for those who build the application knowledge. This requirement for sequencing also makes executing such a language or expert system ineffective on a multiprocessor computer system (utilized for any application, not just natural language), since the frames or unifications are no longer independent time-wise. This sequencing also makes maintenance more difficult and error-prone, since the time dependencies in current implementations are hidden and inconsistent with the model of supposedly independent pieces of knowledge about the application domain.
Many natural language systems use separate storage and processing methods for data describing linguistic properties of words and for data describing the application domain. Frequently, natural language understanding systems utilize completely separate processing steps, where the linguistic analysis produces an output structure describing the sentence which is then used as input by the independent application domain analysis. Both the data separation and the processing separation introduce inefficiencies in processing and reduced accuracy in understanding the natural language command. This separation also makes the creation and updating of the data for an application more complex because information about a single entity in the application domain must be described in two different places with very different methods. This requires a person with significant expertise in linguistics as well as a person with knowledge of the application domain to design and implement the application. Historically, these have been different persons each with specialized training in their area of expertise and this dichotomy continues to be enforced by the development tools provided with current expert systems and natural language systems.
The data required for natural language understanding systems and general expert systems is complex for large commercial projects. This data is typically represented by some combination of lists, structures, and pointers from one data structure to another, with different types of data being represented by different specialized structures. In most systems, data and executable instructions are also represented in very different formats. This proliferation of formats reduces generality and efficiency, limits extensibility, and restricts the access of one type of data while processing another type of data. The proliferation also makes creation of the data more complex, particularly when lists of alternatives and multiple constraints for each alternative are desired.
All of the components of a complex reasoning application such as a natural language understanding system interact so intimately that design decisions in one component have drastic effects on the capabilities, effectiveness, robustness, and extensibility of all of the other components. Therefore, there is a need for a system which is designed in its entirety as a consistent operating whole and there is a need for a system and process that increases overall system efficiency and accuracy in an expert system environment.
An integrated system is described which provides a flexible expert system development and runtime environment with an integrated natural language processor and set-oriented knowledge base. The reasoning module may operate directly from a user input command as an expert system or be called multiple times from the module which interprets a natural language input from the user. The decision module is called by other modules when a value is required. The integrated design of the multiple components allows parallel execution of many processes. The integration also enables consistent definition of differing kinds of complex and interrelated data.
The spreading activation module utilizes the fact that the knowledge base is set-oriented with named relationships between concepts to traverse the knowledge base efficiently. Multiple spreading activation processes may execute robustly in parallel in a multiprocessor system. Chains of related concepts are created which are relevant to the current command. The chains contain both linguistic and application-domain concepts since both kinds of concepts are stored consistently in the knowledge base. These chains provide a small, computationally-tractable number of concepts for evaluation by other processes such as natural language processing which require large amounts of computing time for each evaluated concept.
The natural language processing module accepts a user""s natural language command input one word at a time and adds information to the knowledge base which creates a description of the structure of the entire input sentence. Once this structure is built, the list of concepts produced by the spreading activation module is analyzed to identify those concepts in the knowledge base which most closely match the user""s input command.
The reasoning module executes related, nested logic statements which manipulate the complex, hierarchical facts in the knowledge base. When a value is changed by a logic statement, all previously-executed statements which rely upon that value are automatically re-executed to maintain their correctness. This re-execution is accomplished in a manner which allows optimization and enables robust parallel execution of many processes.
The knowledge base consistently represents all data in a nested set-oriented manner. This results in compatible access to different data types, linguistic and application-domain information, permanent and temporary data, and facts and statements. Extensions to the system are accomplished without changes to the existing set representation. The facility to nest sets and have consistent representations is the foundation of the decision module which interprets varying certainty from multiple sources to select the most relevant value from a given list of values.
The decision module selects the value or values from a list which are most relevant at the moment it is called. This selection process takes into account the execution history of the reasoning module, the certainty and verity of different sources of the values, and a complex set of criteria for selecting the value or values. It thus connects the time-dependent and time-independent aspects of the system.